package com.maze.game.board
{
	import com.maze.game.factory.BaseFactory;
	import com.maze.game.model.base.Base;
	import com.maze.game.model.base.BaseType;
	
	import flash.geom.Point;
	import flash.utils.Dictionary;
	import flash.utils.getDefinitionByName;

	public class BoardSolution
	{
		private var cols:uint;
		private var rows:uint;
		private var data:Array;
		private var startPoint:Point;
		private var exitPoint:Point;
		private var steps:Vector.<Point>;
		private var directions:Vector.<Point>;
		private var stepsSolutions:Vector.<Point>;
		private var resolved:Boolean = false;
		public function get solutions():Vector.<Point>
		{
			return (resolved)?stepsSolutions:steps;
		}

		public function BoardSolution(data:Array)
		{
			this.data = data;
			cols = data[0].length-1;
			rows = data.length-1;
			startPoint = getPointByType(BaseType.START);
			exitPoint = getPointByType(BaseType.EXIT);
			findPath();
		}

		private function getPointByType(type:uint):Point
		{
			var point:Point = new Point();
			var baseType:uint;
			for(var row:uint = 0; row<data.length; row++)
			{
				for(var col:uint = 0; col<data[row].length; col++)
				{
					baseType = data[row][col];
					if(baseType == type)
					{
						point.x = col;
						point.y = row;
					}
				}
			}
			return point;
		}
		
		private function findPath():void
		{
			steps = new Vector.<Point>();
			var step:Point = startPoint.clone();
			addStep(step);

			var success:Boolean = false;
			var failed:Boolean = false;
			while(!success && !failed)
			{
				var nextPoint:Point = getNextMove(step);
				if(nextPoint)
				{
					success = nextPoint.equals(exitPoint);
					step = nextPoint.clone();
					addSolutions(nextPoint);
				} else {
					if(directions && directions.length>0)
					{
						step = directions[directions.length-1];
						directions.pop();
						revertSolutions(step);
					} else {
						failed = true;
					}
				}
			}
			resolved = success;
		}
		
		private function isWallBase(px:Number, py:Number):Boolean
		{
			return data[py][px]==BaseType.WALL;
		}

		private function canMove(step:Point):Boolean
		{
			var isMove:Boolean = true;
			var px:Number = step.x;
			var py:Number = step.y;
			if(px < 0 || py < 0) return false;
			if(px > cols || py > rows) return false;
			for each(var point:Point in steps)
			{
				if(isWallBase(px, py) || point.equals(step))
				{
					isMove = false;
				}
			}
			return isMove;
		}
		
		private function getDistance(step:Point):uint
		{
			return Math.abs(exitPoint.x - step.x)+Math.abs(exitPoint.y - step.y);
		}
		
		private function addStep(step:Point):void
		{
			if(!step) return;
			steps.push(step);
		}
		
		private function getNextMove(step:Point):Point
		{
			var list:Vector.<Point> = get4Steps(step);
			if(list.length==0) return null;
			var stepSelected:Point = list[0];
			var distance:uint = getDistance(stepSelected);
			for each(var point:Point in list)
			{
				if(getDistance(point) < distance)
				{
					stepSelected = point;
				}
			}
			if(list.length>1)
			{
				if(directions == null)
				{
					directions = new Vector.<Point>();
				}
				directions.push(step.clone());
			}
			addStep(stepSelected);
			return stepSelected;
		}

		private function get4Steps(step:Point):Vector.<Point>
		{
			var list:Vector.<Point> = new Vector.<Point>();
			var step2Top:Point = new Point(step.x,step.y-1);
			var step2Right:Point = new Point(step.x+1,step.y);
			var step2Left:Point = new Point(step.x-1,step.y);
			var step2Bottom:Point = new Point(step.x,step.y+1);
			if(canMove(step2Bottom))
				list.push(step2Bottom);
			if(canMove(step2Top))
				list.push(step2Top);
			if(canMove(step2Left))
				list.push(step2Left);
			if(canMove(step2Right))
				list.push(step2Right);
			return list;
		}

		private function addSolutions(step:Point):void
		{
			if(stepsSolutions == null)
				stepsSolutions = new Vector.<Point>();
			stepsSolutions.push(step);
		}
		
		private function revertSolutions(step:Point):void
		{
			if(stepsSolutions == null)
				stepsSolutions = new Vector.<Point>();
			var spliceIndex:Number = -1;
			for(var i:uint = 0; i<stepsSolutions.length; i++)
			{
				if(step.equals(stepsSolutions[i] as Point))
				{
					spliceIndex = i;
				}
			}
			if(spliceIndex>-1)
			{
				stepsSolutions.splice(spliceIndex+1,stepsSolutions.length-spliceIndex-1);
			}
		}
	}
}
